// 约瑟夫环问题
#include <stdio.h>
#include "./model/linked-list.h"

/// @brief 约瑟夫环-数组表示法
/// @param array 数组表示所有的人
/// @param length 表示全部人数
/// @param m 表示每趟报到m的人出列
void josefArray(int array[], int length, int m)
{
	// i表示趟数，j表示每一趟中报的数（计数器），k用于指向当前报号的元素的下标
	int i, j, k = 0;
	// 最后留一人，所以循环n - 1趟
	for (i = 0; i < length - 1; i++)
	{
		// 每一趟从1开始报号
		j = 1;
		// 先让前面报1,2...m - 1的人完成报号
		while (j < m)
		{
			// 如果当前报号人为0说明这个人已经被出列，不进行计数
			while (array[k] == 0)
			{
				// 之所以对长度取模而不是简单的自加
				// 是因为这里使用数组表示环结构，原理和循环队列类似
				k = (k + 1) % length;
			}
			// 每报号一人，j自加，k同步自加并取模
			j++;
			k = (k + 1) % length;
		}
		// 找到报m的人
		// 同样地，先跳过已淘汰的人
		while (array[k] == 0)
		{
			k = (k + 1) % length;
		}
		// 输出被淘汰的人，并标为0
		printf("%d出列！\n", array[k]);
		array[k] = 0;
	}
	// 找到最后一个幸存者
	while (array[k] == 0)
	{
		k = (k + 1) % length;
	}
	printf("最后幸存：%d\n", array[k]);
}

/// @brief 约瑟夫环-链表表示法
/// @param list 存放约瑟夫环的链表（带头循环链表）
/// @param n 链表节点数
/// @param m 表示每趟报到m的人出列
void josefLinked(LinkedList list, int n, int m)
{
	// 指向当前报号元素，以及上一个元素
	LNode *pointer, *prior = list;
	// i表示趟数，j是计数器即每一次报的号
	int i, j;
	// 留最后一个，所以报n - 1趟
	for (i = 0; i < n - 1; i++)
	{
		// 每一次从1开始报
		j = 1;
		pointer = prior->next;
		// 先报到m的前一个
		while (j < m)
		{
			// 如果指针指向了头结点则跳过不计数
			if (pointer == list)
			{
				prior = pointer;
				pointer = pointer->next;
				continue;
			}
			prior = pointer;
			pointer = pointer->next;
			j++;
		}
		// 此时指向的元素是要出列的元素，进行删除
		// 同样的如果指针指向了头结点则跳过
		if (pointer == list)
		{
			prior = pointer;
			pointer = pointer->next;
		}
		printf("%d出列！\n", pointer->data);
		prior->next = pointer->next;
		free(pointer);
	}
	// 找到最后一个
	pointer = prior->next;
	// 同样考虑跳过头结点
	if (pointer == list)
	{
		pointer = pointer->next;
	}
	printf("最后幸存：%d\n", pointer->data);
}

int main()
{
	int array[100], i;
	LinkedList list = createList(array, 100);
	LNode *p = list->next;
	for (i = 0; i < 100; i++)
	{
		array[i] = i + 1;
		p->data = i + 1;
		if (i == 99)
		{
			p->next = list;
		}
		p = p->next;
	}
	josefArray(array, 100, 5);
	printf("----------------------\n");
	josefLinked(list, 100, 5);
	return 0;
}